leetcode刷题记录12

发表于   |   分类于

介绍12

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

思路12

试了几次之后发现，除了2,3这两个输入以外，不管输啥，结果都是由2,3组成的，再仔细观察下，2的个数和n除以3的余数有关，然后就搞定了。算是摸清套路了，凡是这种看起来巨复杂的题，都是有内在数学规律的。。。

代码12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==2:
            return 1
        elif n==3:
            return 2
        else:
            t=n/3
            k=n%3
            if k==1:
                s=3**(t-1)*4
            elif k==2:
                s=3**t*2
            else:
                s=3**t
            return s